Asynchronous Transfer Mode (ATM) is the technology of choice for Broadband Integrated Services Digital Network (B-ISDN), a communications standard that supports a range of data, voice, image, video, and multimedia services, with different grade of service (GoS) objectives, such as call blocking probability, as well as quality of service (QoS) objectives, such as cell loss probability and cell transfer delay. This is achieved with careful resource management, i.e., controlled access of network resources, such as link bandwidth and switch buffer resources.
Resource management controls can be implemented at a number of levels in an ATM network. Controls can be applied to Virtual Channel Connections (VCCs), which are connections of virtual channel links (segments of unidirectional transport of ATM cells between a point where a virtual channel identifier (VCI) is assigned to the point where this value is translated or removed), and Virtual Path Connections (VPCs) which are a concatenation of virtual path links, which are terminated by points where the virtual path identifier (VPI) is assigned and translated or removed. FIG. 1 shows an illustration of VCCs and VPCs. Typically, VCCs are set up on demand, while VPCs are preestablished (provisioned), i.e., with bandwidth and buffer resources allocated a priori. Thus, to set up an on-demand connection, e.g., a VCC from end host A to end host B in FIG. 1, Connection Admission Control (CAC) functions and switch fabric configurations are only performed at the terminating points of each VP segment, e.g., at switches SW1 and SW2. As is known, provisioning VPCs offers a number of advantages such as: reducing end-to-end VCC setup delay; use in self-healing networks due to faster rerouting and restoring speeds; a reduction in network "switching" costs since VP cross-connects can be used in parts of the network; and, use in certain applications such as IP-over-ATM networks, where provisioned VPC's improve performance by avoiding a connection setup to transfer connectionless IP packets across an ATM network, and wireless ATM networks where provisioned VPCs between adjacent base stations allows simplified mobile handoffs.
By way of background, VPCs are of two types: homogeneous, if they only support calls of a single traffic class, and heterogeneous, if they support multiple classes of traffic. As the underlying source model of cell arrival rates at a network connection has been shown to be reasonably modeled as a Markov Modulated (MM) process, the modulating process may be represented as a continuous time Markov chain with state transition rates [m.sub.ij ], i, j .epsilon. {1, . . . , K}, represented as a matrix M. Based on the characteristics of the modulated process, two types of source models are commonly used, the Markov Modulated Poisson Process (MMPP) model and the Markov Modulated Fluid (MMF) model. In the MMPP model, in any given state i of the Markov process, cells are generated according to a Poisson process with intensity R.sub.i. On the other hand, an MMF source, in state i, generates information as a continuous flow (fluid) with a rate R.sub.i. In either model, the source intensities are represented as a K.times.1 vector, R, and the source is characterized by the tuple [M,R]. When cells from multiple sources arrive at a switch, as shown in FIG. 2, the cells are stored in a buffer until the destination port/link is free. Due to finite buffer sizes and the stochastic nature of the sources, buffer overflow leads to cell loss. Thus, as shown in FIG. 2, an important QoS criteria for a connection is the Cell Loss Ratio (CLR), which is the ratio of the total number of cells that are dropped due to buffer overflow to the total number of cells that arrive at the switch, and the Cell Transfer Delay (CTD), which is the time spent in a buffer, before being switched out.
A drawback of using provisioned VPCs with preallocated capacity is that network utilization (transmission efficiency) is reduced since link and node resources are partitioned (rather than shared). This effect is especially true if the resource allocations to VPCs are made allowing for uncertainty in traffic characterization.
The effect of varying traffic patterns can be sharply reduced by using a scheme which dynamically adjusts VPC resource allocations based on usage.
One method for dynamically realizing changes in VPC routes and resource allocations is to use control plane (signaling) software on switches as is done with Soft Provisioned Virtual Circuits (SPVCs). This method inherently possesses two drawbacks in that it uses a sequential node-by-node setup and configuration procedure which may result in excessive and unacceptable VPC adjustment delays and, further requires additional software to monitor VPCs and initiate adjustments, on already overloaded switches.
Several other schemes for the creation and maintenance of VPCs in ATM networks have been proposed. These are largely optimization based schemes for assigning bandwidths to VPCs such that the call blocking probability is minimized. These schemes involve the solution of a complex, non-linear optimization with non-linear constraints. Although these problems may be simplified by using approximations, currently, the optimization is solved periodically in a centralized fashion and the results down-loaded to the switches. Additionally, due to their centralized nature, these schemes do not scale well for large networks and fault tolerance becomes a problem since the server which performs the optimization could fail. Although these schemes attempt to achieve optimal call blocking probability, in reality, the approximations and simplifications needed to make the optimization feasible, remove any guarantees of optimality. Also, since the optimization is complicated, it cannot be performed often, thus further compromising the optimality of the assigned bandwidths.
Dynamic management of VPC routes and resource allocations can be done by continuously monitoring the network and reacting to repeated congestion patterns, and topological changes caused by failures and additions of network elements such as links and nodes. The recently standardized Simple Network Management Protocol (SNMP) and the ATM Management Information Base (MIB) currently provide the basis for dynamic solutions. For instance, MIBs reflect the current conditions of the network elements by enabling network managers to communicate with agents on network elements to read and write MIB variables in order to provide dynamic management of VPCs. However, there are several drawbacks in performing dynamic management of VPCs using MIB reads and writes: First, is its inefficiency in a distributed solution which would require various network managers distributed throughout the network to constantly read these MIB variables from the switches thus negatively impacting the performance of the switch agents. Second, is its inefficiency resulting from writing MIB variables to realize changes in VPC routes and resource allocations which can be time consuming.
Thus, besides being dynamic, the VPC management scheme needs to be distributed for the reason that a centralized solution does not scale well with the size of the network, and is also very poor from a fault tolerance perspective.
A distributed scheme for control of VP bandwidths has been proposed, e.g., in S. Shioda and H. Uose, "Virtual path bandwidth control method for ATM networks: successive modification method," IEICE Trans., vol. E74, pp. 4061-4068, Dec. 1991. This scheme is a heuristic which works on the observed call blocking probability on the different VPs, but has drawbacks in that exactly one VPC is allowed between each pair of switches which is a severe restriction, and, the route of each VPC is precomputed and fixed which is not reasonable where a network state is constantly changing as does the "best" route between a pair of nodes.
It would thus be highly desirable to aim for a solution to the VPC bandwidth/buffer/route management problem that addresses the drawbacks and shortcomings of existing dynamic VPC bandwidth management methods. Such a solution to the VPC bandwidth/buffer/route management problem should be scalable with respect to the size of the network and precludes any centralized approaches. Furthermore, such a solution should be robust and be capable of handling network state changes such as network element additions and failures. Moreover, such a solution should not assume fixed precomputed routing of the VPCs but rather provide for the routing VPCs according to the "best" paths, which could change with time as the network state changes. Additionally, the solution should be able to take advantage of existing standards and interwork with them.